package com.wfm.niuke.huisu;
public class PTwo00岛屿数量 {
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    // 这种是先判断条件，再进去递归
//    public int numIslands(char[][] grid) {
//        boolean[][] visited = new boolean[grid.length][grid[0].length];
//        int cnt = 0;
//        for (int i = 0; i < grid.length; i++) {
//            for (int j = 0; j < grid[0].length; j++) {
//                if(grid[i][j]=='1'&&!visited[i][j]){
//                    dfs(grid,i,j,visited);
//                    cnt++;
//                }
//            }
//        }
//        return cnt;
//    }
//    void dfs(char[][] grid,int i ,int j,boolean[][] visited){
//        visited[i][j] = true;
//        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
//        for (int[] dir : directions) {
//            int newi = i + dir[0], newj = j + dir[1];
//            if(inArea(grid, newi , newj)){
//                if (!visited[newi][newj]&&grid[newi][newj]=='1') {
//                    dfs(grid,newi,newj,visited);
//                }
//            }
//
//        }
//    }
//
//    private boolean inArea(char[][] grid, int i, int j) {
//        if(i<0||i>=grid.length||j<0||j>=grid[0].length) return false;
//        else return true;
//    }

    // 这种是一股脑进去递归，再判断条件
    public int numIslands(char[][] grid) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int cnt = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]=='1'&&!visited[i][j]){
                    dfs(grid,i,j,visited);
                    cnt++;
                }
            }
        }
        return cnt;
    }
    void dfs(char[][] grid,int i ,int j,boolean[][] visited){
        if(!inArea(grid,i,j)){
            return;
        }
        if(visited[i][j]){
            return;
        }
        if(grid[i][j]!='1'){
            return;
        }
        visited[i][j] = true;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            dfs(grid,newi,newj,visited);
        }
    }

    private boolean inArea(char[][] grid, int i, int j) {
        if(i<0||i>=grid.length||j<0||j>=grid[0].length) return false;
        else return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PTwo00岛屿数量().new Solution();
        char[][] chars = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };
        int i = solution.numIslands(chars);
        System.out.println(i);
    }
}